940F - Machine Learning - CodeForces Solution

#pragma GCC optmize ("O3")

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>

const int Max = 2e5 + 10;
const int Sq = 2200;
std::vector<int64_t> array;
std::vector<size_t> T;
std::vector<size_t> L;
std::vector<size_t> R;
std::vector<std::pair<size_t, int64_t>> F;
std::vector<std::pair<size_t, int64_t>> B;
int ans[Max];
std::map<int64_t, int64_t> cnv;
int l, r, t;
int cnt[Max * 2];
int ccnt[Max];

inline bool cmp(size_t i, size_t j) {
    if (T[i] / Sq != T[j] / Sq) {
        return T[i] / Sq < T[j] / Sq;
    } else if (L[i] / Sq != L[j] / Sq) {
        return L[i] / Sq < L[j] / Sq;
    }
    return R[i] < R[j];
}

inline void Add(size_t index) {
    --ccnt[cnt[array[index]]];
    ++cnt[array[index]];
    ++ccnt[cnt[array[index]]];
}

inline void Del(size_t index) {
    --ccnt[cnt[array[index]]];
    --cnt[array[index]];
    ++ccnt[cnt[array[index]]];
}

inline void Update(size_t index, int64_t new_value) {
    if (l <= index && index <= r) {
        Del(index);
        array[index] = new_value;
        Add(index);
    } else {
        array[index] = new_value;
    }
}

enum QueryType {
    RESEARCH = 1,
    CHANGE = 2
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    size_t n, q;
    std::cin >> n >> q;
    array.resize(n + 1, 0);
    for (size_t i = 1; i <= n; i++) {
        std::cin >> array[i];
        if (!cnv[array[i]]) {
            cnv[array[i]] = static_cast<int32_t>(cnv.size()) + 1;
        }
        array[i] = cnv[array[i]];
    }
    size_t timeline = 1;
    size_t research_counter = 1;
    L.resize(q + 1, 0);
    R.resize(q + 1, 0);
    T.resize(q + 1, 0);
    F.resize(q + 1);
    B.resize(q + 1);
    for (size_t i = 1; i <= q; i++) {
        int query;
        std::cin >> query;
        if (query == QueryType::RESEARCH) {
            std::cin >> L[research_counter] >> R[research_counter];
            T[research_counter] = timeline;
            ++research_counter;
        } else if (query == QueryType::CHANGE) {
            size_t p;
            int64_t x;
            std::cin >> p >> x;
            if (!cnv[x]) {
                cnv[x] = static_cast<int64_t>(cnv.size()) + 1;
            }
            x = cnv[x];

            F[timeline] = std::make_pair(p, x);
            ++timeline;
            B[timeline] = std::make_pair(p, array[p]);
            array[p] = x;
        }
    }
    std::vector<int> srt;
    for (int i = 1; i < research_counter; i++) {
        srt.push_back(i);
    }
    sort(srt.begin(), srt.end(), cmp);
    while (timeline > 1) {
        array[B[timeline].first] = B[timeline].second;
        --timeline;
    }
    l = 1, r = 0, t = 1;
    for (int32_t i: srt) {
        while (r < R[i]) {
            ++r;
            Add(r);
        }
        while (l > L[i]) {
            --l;
            Add(l);
        }
        while (r > R[i]) {
            Del(r);
            --r;
        }
        while (l < L[i]) {
            Del(l);
            ++l;
        }
        while (t > T[i]) {
            Update(B[t].first, B[t].second);
            --t;
        }
        while (t < T[i]) {
            Update(F[t].first, F[t].second);
            ++t;
        }
        int ANS = 1;
        while (ccnt[ANS] >= 1) {
            ++ANS;
        }
        ans[i] = ANS;
    }
    for (size_t i = 1; i < research_counter; i++) {
        std::cout << ans[i] << '\n';
    }
}